-*- Mode: Text -*-

;;; File:  AutoClass:doc;search.text
;;;--------------------------------------------------------------------------;;;
;;;  AUTOCLASS 3.0  Released 5/11/90    contact:  Taylor@pluto.arc.nasa.gov  ;;;
;;;  by P. Cheeseman, J. Stutz, R. Hanson, W. Taylor 			     ;;;
;;;  NASA Ames Research Center, MS 244-17, Moffett Field, CA 94035           ;;;
;;;                                                                          ;;;
;;;  Copyright (C) 1990 Research Institute for Advanced Computer Science.    ;;;
;;;  All rights reserved.  The RIACS Software Policy contains specific       ;;;
;;;  terms and conditions on the use of this software, and must be           ;;;
;;;  distributed with any copies.  THIS FILE MAY BE REDISTRIBUTED.  This     ;;;
;;;  copyright and notice must be preserved in all copies made of this file. ;;;
;;;--------------------------------------------------------------------------;;;




Searching For Good Classifications

Now that you have succeeded in describing your data with a header file
and model file that passes AUTOCLASS-INPUT-CHECK, you are ready to
actually use Autoclass to classify your data.  (At last!)

The main function to use in finding a good classification of your data
is AUTOCLASS-SEARCH, and using it will take most of the computation
time.  A plain vanilla search can be invoked with:

(AUTOCLASS-SEARCH :DATA-FILE <your-data-file>
	          :HEADER-FILE <your-header-file>
                  :MODEL-FILE <your-model-file>)

The sample-run that comes with Autoclass shows some sample searches, and
browsing these is probably the fastest way to get familiar with how to
do searches.  The remainder of this section describes how to do searches
in somewhat more detail.

	
What Results Are

Autoclass is looking for the best classification(s) of the data it can find.
A classification is composed of: 
 1) a set of classes, each of which is described by a set of class 
    parameters, which specify how the class is distributed along the 
    various attributes.  For example, "height normally distributed with 
    mean 4.67 ft and standard deviation .32 ft", 
 2) a set of class weights, describing what percentage of cases are 
    likely to be in each class. 
 3) a probabilistic assignment of cases in the data to these classes.  
    I.e. for each case, the relative probablity that it is a member of
    each class.  

As a strictly Bayesian system (accept no substitutes!), the quality
measure Autoclass uses is the total probability that, had you known
nothing about your data or its domain, you would have found this set of
data generated by this underlying model.  This includes the prior
probability that the "world" would have chosen this number of classes,
this set of relative class weights, and this set of parameters for each
class, and the likelihood that such a set of classes would have generated
this set of values for the attributes in the data cases.

These probabilities are typically very small, in the range of e^-30000,
and so are usually expressed in exponential notation.

WHAT RESULTS MEAN

It's important to remember that all of these probabilities are GIVEN
that the real model is in the model family that Autoclass has restricted
its attention to.  If Autoclass is looking for Guassian classes and the
real classes are Poisson, then the fact that Autoclass found 5 Guassian
classes may not say much about how many Poisson classes there really are.

The relative probability between different classifications found can be
very large, like e^1000, so the very best classification found is
usually overwhelmingly more probable than the rest (and overwhelmingly
less probable than any better classifications as yet undiscovered).  If
Autoclass should manage to find two classifications that are within
about exp(5-10) of each other (i.e. within 100 to 10,000 times more
probable) then you should consider them to be about equally probable, as
our computation is usually not more accurate than this (and sometimes
much less).

HOW IT WORKS

Autoclass repeatedly creates a random classification and then tries to
massage this into a high probability classification though local changes,
until it converges to some "local maximum".  It then remembers what it
found and starts over again, continuing until you tell it to stop.  Each
effort is called a "try", and the computed probability is intended to
cover the whole volume in parameter space around this maximum, rather
than just the peak.

The standard approach to massaging (using #'CONVERGE as the :TRY-FN) is to 
 1) Compute the probabilistic class memberships of cases using the class
    parameters and the implied relative likelihoods.
 2) Using the new class members, compute class statistics (like mean)
    and revise the class parameters.
and repeat till they stop changing.  Most sophisticated approaches try to 
do more things during the converge, such as merging and splitting classes
(using #'MERGE&SPLIT-SEARCH2 as :TRY-FN).  See *try-fn-list* for a list
of these.

WHEN TO STOP

You can tell AUTOCLASS-SEARCH to stop by giving a :MAX-DURATION (in
seconds) argument at the beginning, or by typing a "q" at the end.
Deciding when to stop is a judgment call and it's up to you.  Since the
search includes a random component, there's always the chance that if
you let it keep going it will find something better.  So you need to
trade off how much better it might be with how long it might take to
find it.  The search status reports that are printed when a new best
classification is found are intended to provide you information to help
you make this tradeoff.

One clear sign that you should probably stop is if most of the
classifications found are duplicates of previous ones (flagged by "dup"
as they are found).  This should only happen for very small sets of data
or when fixing a very small number of classes, like two.

WHAT GETS RETURNED

Just before returning, AUTOCLASS-SEARCH will give short descriptions of
the best classifications found.  How many will be described can be
controlled with :N-FINAL-SUMMARY.

AUTOCLASS-SEARCH returns two values, a search object and a vector of the
best classifications found so far, starting with the very best.  The
search object describes the search so far, and includes slots for how
long the search has taken, the number of tries, and the rate of
duplication.  It also contains a vector of "search-try"s, which describe
each try.  (Some tries remember a full classification, but most of
them just remember a few statistics.)

By default AUTOCLASS-SEARCH will write out a number of files, both at
the end and periodically during the search (in case your system crashes
before it finishes).  These files will all have the same name, which
you can specify using :OUTPUT-FILES-DEFAULT, and differ only in their 
file extension.  

A .LOG file will hold a listing of most of what was printed to the
screen during the run, unless you set :LOG-FILE-P to nil to say you want
no such foolishness. Unless :RESULTS-FILE-P, a .RESULTS or .DUMP file
will hold the best classifications that were returned (which one depends 
on :SAVE-COMPACT-P), and unless :SEARCH-FILE-P, a .SEARCH file will hold
the search object.

HOW TO GET STARTED

There are a number of different ways to invoke AUTOCLASS-SEARCH. The
simplest is to give a :DATA-FILE, :HEADER-FILE and :MODEL-FILE.  Another
is to give :CLSF a classification object, such as is returned by
GENERATE-CLSF.  To restart a previous search, you can either pass a
search object in to :SEARCH, or use :OUTPUT-FILES-DEFAULT to indicate
what previous .SEARCH and .RESULTS/.DUMP files to use.  (Both of these
files are needed to restart from disk.)  Actually, no matter what
arguments you give, AUTOCLASS-SEARCH will try to find a previous
compatible search to continue, and will restart using it if found.  To
force a new search instead of restarting an old one, give the argument
:FORCE-NEW-SEARCH-P T.

If a previous search is continued, the message "RESTARTING SEARCH" will
be given instead of the usual "BEGINNING SEARCH".  It is generally
better to continue a previous search than to start a new one, unless
you are trying a significantly different search method, in which case
statistics from the previous search may mislead the current one.

STATUS REPORTS

Unless :REPORT-P is nil, a running commentary on the search will be
printed to :STREAM.  After each try a very short report (only a few
characters long) is given.  After each new best classification, a longer
report is given, but no more often than :MIN-REPORT-PERIOD (in seconds).
On a Symbolics Lisp Machine, :PLOT T will result in a scatter plot of
the classification being shown.  :USER-REPORT is a hook to allow users
to describe the new best classification as they wish.  
    (FUNCALL user-report :CLSF the-new-best-classification) 
is what will be called.

A warning to the wise (or whoever).  Some environments may, after a
screen full of text, suspend a search that you had meant to run
overnight on the excuse of "waiting for the user to tell me its all
right to print more".  On a Lisp Machine you may want to do something
like the following to avoid that.  
(SEND *TERMINAL-IO* :SET-DEEXPOSED-TYPEOUT-ACTION :PERMIT) 
(SEND *TERMINAL-IO* :SET-MORE-P NIL)

SEARCH VARIATIONS

AUTOCLASS-SEARCH by default uses certain standard search methods, and
variations on these standards are provided in case your problem is one
that happens to benefit from them.  In general these methods will
result in finding better classifications faster or slower, and so should
be considered primarily performance hooks.  The defaults have been
chosen so as to be robust, giving even performance across many problems.
Alternatives to the defaults may do better on some problems, but may do
substantially worse on others.

The standard way to create a random classification to begin a try is
:START-FN #'RANDOM-SET-CLSF.  Alternatives are given in *start-fn-list*.
See the individual functions for documentation.  :-)

The standard way to converge the initial classification to a local
maximum is :TRY-FN #'CONVERGE.  Alternatives are given in *try-fn-list*,
listed in order of preference.  See the individual functions for
documentation.   

The :START-FN and :TRY-FN will be passed the entire argument list given
to AUTOCLASS-SEARCH, to facilitate experimentation.  One should check the
individual function argument lists to see what is appropriate.  Certain
arguments are common to many.  :MIN-CYCLES and :MAX-CYCLES control the
number of basic convergence cycles in several convergence functions.
:DELTA-FACTOR similarily controls the absolute rate of convergence at
which convergence is terminated.  :REL-ERROR (used in #'%=) determines
the allowed degree of difference in tests for equivalence of classes or
classifications.  

HOW MANY CLASSES?

Each new try begins with a certain number of classes and ends up with a
slightly smaller number, as some classes may drop out of the converge.
In general, you want to begin the try with some number of classes that
previous tries have indicated look promising, and you want be sure you
are fishing around elsewhere in case you missed something before.

:N-CLASSES-FN #'RANDOM-J-FROM-LN-NORMAL is the default way to make this
choice.  It fits a log-normal to the number of classes (usually called
"j" for short) of the best classification so far, and randomly selects
from that.  #'RANDOM-J-IN-WINDOW is an alternative.

To start the game off, the default is to go down :START-J-LIST for the
first few tries, and then switch to :N-CLASSES-FN.  If one wants to
always look for, say, three classes, one can use :FIXED-J and override
the above.  Search status reports will describe what the current method
for choosing j is.

DO I HAVE ENOUGH MEMORY?

Internally, the storage requirements in the current system are of order:
n-classes-per-clsf * (n-data + n-stored-clsfs*n-attr*n-attr-values) This
depends on the number of cases, the number of attributes, the values per
attribute (use 2 if a number), and the number of classifications stored
away for comparison to see if others are duplicates, controlled by
:MAX-N-STORE.  The search process does not itself consume significant
memory, but storage of the results may do so.

Disk space taken up by the log file will of course depend on the duration
of the search.  :N-SAVE determines how many best classifications are
saved into :results-file, and returned at the end of the search.
:SAVE-COMPACT-P controls whether the files are saved as binary.  Binary
files are faster and more compact, but cannot be shared between say a sun
and a symbolics.  If the time to save is a problem, consider increasing
:MIN-SAVE-PERIOD.  Files are saved to disk this often if there is
anything different to report.

JUST HOW SLOW IS IT?

Compute time is of order: n-data * n-attr * n-classes * n-tries
* converge-cycles-per-try. The major uncertainties in this are the
number of basic back and forth cycles till converge in each try, and of
course the number of tries.  This is typically 10-100 for :TRY-FN
#'CONVERGE and can be much larger for alternatives.  The largest problem
we have worked on (5,425 cases, 93 attributes, and 88 classes) took ~3
hours per a single cycle.

THOSE ARGUMENTS AGAIN

(defun AUTOCLASS-SEARCH
(&rest args &key clsf
;; if just pass in clsf, will check for old search under default names

data-file (header-file "") (model-file "")
;; if no clsf or previous search, will make a clsf from these files

output-files-default
;; a file name to use for all of log, results, search, each w/ diff extension

(log-file-p t)
;; unless nil, will write record of messages to file with .log extension

(results-file-p t)
;; unless nil, will write best clsfs seen to file ends .results or .dump

(search-file-p t)
;; unless nil, will write the search to a file with .search extension

search
;; a search structure returned from recent search, to continue with now

force-new-search-p
;; if non-nil, will ignore any previous search results

(try-fn (first *try-fn-list*))
;; will repeatedly call this function to try and find better classifications
;; will do (APPLY try-fn clsf :allow-other-keys t args) and it must either
;; return a new clsf, or modify the one passed to it.  see *try-fn-list*

(start-fn (first *start-fn-list*))
;; how to initialize the cslf each time.  See *start-fn-list*

rel-error
;; passed to clsf-$-%= when deciding if a new clsf is duplicate of old

(n-classes-fn (first *n-classes-fn-list*))
;; will call this function to decide how many classes to start next try with
;; based on best clsfs so far. see *n-classes-fn-list*

(start-j-list '(1 2 3 5 7 10 15 25))
;; initially will try these numbers of classes, so not narrow too quickly

fixed-j
;; when non-nil, overrides above 2 args, and always uses this j-in

(report-p t) (stream *standard-output*)
;; a running report on the search will be sent to this stream, if report-p

(user-report #'(lambda (&rest ignore) nil))
;; call (funcall user-report :clsf clsf) on each new best classification

(min-report-period 30)
;; will wait at least this time since last report till report verbosely again

max-duration
;; the search will end this time from now if it hasn't already

plot
;; will show graphics of new best clsf with report, (symbolics only)

(n-save 2)
;; save this many clsfs to disk in results-file, and in search that return
;; if 0, means don't save anything, and search at end is uncontinuable

(min-save-period 1800)
;; to protect against possible crash, will save to disk this often

(save-compact-p t)
;; should saved files be as compact as possible, even if not readable-p

(max-n-store 100)
;; don't store any more than this many clsfs internally

(n-final-summary 10)
;; print out descriptions of this many of the searches at the end

&allow-other-keys
;; like: delta-factor n-ave n-best-track used in #'coverge







